﻿//39. 组合总和
//给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
// 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
//并以列表形式返回。你可以按 任意顺序 返回这些组合。
//candidates 中的 同一个 数字可以 无限制重复被选取 。
//如果至少一个数字的被选数量不同，则两种组合是不同的。
//对于给定的输入，保证和为 target 的不同组合数少于 150 个。


class Solution {
public:
    vector<int> v;
    void dfs(vector<vector<int>>& ret, vector<int>& num, int target, int search_index)
    {
        //递归出口
        if (target == 0)
        {
            ret.push_back(v);
            return;
        }
        else if (target < 0)
        {
            return;
        }
        //递归
        else
        {
            int n = num.size();
            for (int i = search_index; i < n; i++)
            {
                v.push_back(num[i]);
                dfs(ret, num, target - num[i], i);
                //回溯
                v.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int>> ret;
        vector<int> num;
        for (auto& e : candidates)
        {
            if (e <= target)
            {
                num.push_back(e);
            }
        }
        dfs(ret, num, target, 0);
        return ret;
    }
};